#define _CRT_SECURE_NO_WARNINGS 1

#include<stack>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    
};

class Solution {
public:

    bool dealpath(TreeNode* root, stack<TreeNode*>& path, TreeNode* x)
    {
        if (root == nullptr)
            return false;
        path.push(root);
        if (root == x)
            return true;
        if (!dealpath(root->left, path, x))
        {
            if (!dealpath(root->right, path, x))
            {
                path.pop();
                return false;
            }
            return true;
        }
        else
            return true;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pPath;
        stack<TreeNode*> qPath;
        dealpath(root, pPath, p);
        dealpath(root, qPath, q);

        while (pPath.size() != qPath.size())
        {
            if (pPath.size() > qPath.size())
            {
                pPath.pop();
            }
            else
            {
                qPath.pop();
            }
        }

        while (pPath.top() != qPath.top())
        {
            pPath.pop();
            qPath.pop();
        }
        return pPath.top();
    }
};